/*
 * GrafoSudoku.java
 *
 * Criado em 1 de Junho de 2007, 20:23
 */

package dharsudoku.core.grafo;

import dharsudoku.core.vertice.Vertice;
import dharsudoku.core.vertice.VerticeCartesiano;
import dharsudoku.core.vertice.VerticeCoord;

/**
 * Implementa um grafo que representa um tabuleiro GrafoSudoku 9x9
 *
 * @author Rodrigo
 */
public class GrafoSudoku extends Grafo{
    
    /**
     * Cria um novo sudoku vazio
     */
    public GrafoSudoku() {
	
	/* Cria vertices */
	for (int x = 1; x <= 9; x++)
	    for (int y = 1; y <= 9; y++) {
	    this.adicionar(new VerticeCoord(0, x, y));
	    }
	
	/* Efetua ligações */
	for (java.util.Iterator i = this.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCoord A = (VerticeCoord)i.next();
	    
	    for (java.util.Iterator j = this.getVertices().iterator(); j.hasNext(); ) {
		VerticeCoord B = (VerticeCoord)j.next();
		
		/* Verifica condição para ter aresta entre A e B */
		if ((A != B) && (!A.isAdjacente(B)) &&
			((A.getX() == B.getX() || (A.getY() == B.getY()) ||
			((A.getX()-1)/3 == (B.getX()-1)/3 && (A.getY()-1)/3 == (B.getY()-1)/3)))) {
		    try {
			this.adicionarAresta(A, B);
		    } catch (Exception ex) {
			continue;
		    }
		}
	    }
	}
    }
    
    /**
     * Retorna valor da célula.
     * @param x Coordenada x(1-9)
     * @param y Coordenada y(1-9)
     * @return Valor da célula na coordenada, -1 se coordenada é inválida
     */
    public int getValor(int x, int y) {
	
	/* Itera vertices */
	for (java.util.Iterator i = this.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCoord v = (VerticeCoord)i.next();
	    
	    if (v.getX() == x && v.getY() == y)
		return v.getId();
	}
	
	return -1;
    }
    
    /**
     * Verifica se é possivel atribuir um dado valor a
     * uma célula do sudoku.
     * @param x Coordenada x(1-9)
     * @param y Coordenada y(1-9)
     * @param valor Valor da célula(1-9), ou 0 para vazio
     * @return Verdadeiro se é possivel inserir valor
     */
    public boolean valorPossivel(int x, int y, int valor) {
	
	if (valor == 0 || valor < 1 || valor > 9)
	    return false;
	
	/* Itera vertices */
	for (java.util.Iterator i = this.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCoord v = (VerticeCoord)i.next();
	    
	    if (v.getX() == x && v.getY() == y) {
		/* Itera vertices adjacentes */
		for (java.util.Iterator j = v.getAdjacentes().iterator(); j.hasNext(); ) {
		    VerticeCoord u = (VerticeCoord)j.next();
		    
		    if (u.getId() == valor)
			return false;
		}
		return true;
	    }
	}
	return false;
    }
    
    /**
     * Seta valor de uma célula de uma coordenada.
     * @param x Coordenada x(1-9)
     * @param y Coordenada y(1-9)
     * @param valor Valor da célula(1-9), ou 0 para vazio
     * @return Verdadeiro se foi possível alterar o valor
     */
    public boolean setValor(int x, int y, int valor) {
	
	if (valor < 0 || valor > 9)
	    return false;
	
	/* Itera vertices */
	for (java.util.Iterator i = this.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCoord v = (VerticeCoord)i.next();
	    
	    if (v.getX() == x && v.getY() == y) {
		if (valor == 0) {
		    v.setId(valor);
		    return true;
		} else {
		    /* Itera vertices adjacentes */
		    for (java.util.Iterator j = v.getAdjacentes().iterator(); j.hasNext(); ) {
			VerticeCoord u = (VerticeCoord)j.next();
			
			if (u.getId() == valor)
			    return false;
		    }
		    v.setId(valor);
		    return true;
		}
	    }
	}
	return false;
    }
    
    /**
     * Zera jogo de sudoku: apaga todos os números
     */
    public void zerar() {
	/* Itera vertices */
	for (java.util.Iterator i = this.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCoord v = (VerticeCoord)i.next();
	    
	    v.setId(0);
	}
    }
    
    public boolean resolver() {
	/* Cria grafo completo Km, para m = 9 */
	Grafo completo = new GrafoCompleto(9);
	
	/* Cria produto cartesiano deste sudoku e Km */
	Grafo universo = this.getProdutoCartesiano(completo);
	
	Grafo solucao = new Grafo();
	
	/* Adiciona a solução todos as celulas do sudoku ja marcadas */
	/* Itera vertices */
	for (java.util.Iterator i = this.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCoord v = (VerticeCoord)i.next();
	    
	    if (v.getId() != 0) {
		/* Percorre todo conjunto de vertices do universo */
		for (java.util.Iterator j = universo.getVertices().iterator(); j.hasNext(); ) {
		    VerticeCartesiano u = (VerticeCartesiano)j.next();
		    
		    if (((VerticeCoord)u.getU()).getX() == v.getX() && ((VerticeCoord)u.getU()).getY() == v.getY() &&
			    u.getV().getId() == v.getId()) {
			u.setId(-1);
			solucao.adicionar(u);
		    }
		}
	    }
	}
	
	java.util.Set solucoes = new java.util.HashSet();
	
	/* Tenta encontrar o maior conjunto independete */
	for (java.util.Iterator i = universo.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCartesiano v = (VerticeCartesiano)i.next();
	    
	    if (!solucao.possui(v) && !solucao.existeConexao(v)) {
		
		solucao.adicionar(v);
		getIndependenteMaximo(solucao, universo);
		
		solucoes.add(solucao);
		
		if (solucao.getTamanho() == 81)
		    break;
		else
		    solucao.remover(v);
	    }
	}
	
	if (solucao.getTamanho() != 81) {
	    
	    for (java.util.Iterator i = solucoes.iterator(); i.hasNext(); ) {
		Grafo A = (Grafo)i.next();
		
		
		for (java.util.Iterator j = solucoes.iterator(); j.hasNext(); ) {
		    Grafo B = (Grafo)j.next();
		    
		    if (A != B) {
			
			solucao = A.getInterseccao(B);
			getIndependenteMaximo(solucao, universo);
			
			if (solucao.getTamanho() == 81)
			break;
		    }
		}
		
		if (solucao.getTamanho() == 81)
		    break;
	    }
	}
	
	System.err.println(solucao.isIndependente() + " = " + solucao.getTamanho());
	
	/* Percorre todo conjunto de vertices de solucao */
	for (java.util.Iterator i = solucao.getVertices().iterator(); i.hasNext(); ) {
	    VerticeCartesiano v = (VerticeCartesiano)i.next();
	    
	    this.setValor(((VerticeCoord)v.getU()).getX(), ((VerticeCoord)v.getU()).getY(), v.getV().getId());
	}
	
	return (solucao.getTamanho() == 81);
    }
    
    
    /**
     * @param independente SUbconjunto independente
     * @param universo Conjunto universo
     */
    private static boolean aumentarConjuntoIndependente(Grafo independente, Grafo universo) {
	
	boolean aumentou;
	boolean aumentouUmaVez = false;
	
	do {
	    aumentou = false;
	    Vertice b = null;
	    int m = 0;
	    
	    /* Percorre vertices deste grafo */
	    for (java.util.Iterator i = universo.getVertices().iterator(); i.hasNext(); ) {
		Vertice v = (Vertice)i.next();
		
		/* Verifica se nao possui vertice */
//		if (!independente.possui(v) && !independente.existeConexao(v)) {
//
//		    independente.adicionar(v);
//
//		    aumentou =  true;
//		    aumentouUmaVez = true;
//
//		    if (independente.getTamanho() == 81)
//			return true;
//		}
		if (!independente.possui(v) && !independente.existeConexao(v)) {
		    int n = (20+8) - universo.conexoes(v, independente);
		    if (n > m) {
			b = v;
			m = n;
		    }
		}
	    }
	    
	    if (b != null) {
		aumentou = true;
		aumentouUmaVez = true;
		
		independente.adicionar(b);
		
		if (independente.getTamanho() == 81)
		    return true;
	    }
	    
	}while (aumentou);
	
	return aumentouUmaVez;
    }
    
    /**
     * Aumenta um subconjunto independete dado até o seu máximo
     * dentro do grafo.
     * @param independente SUbconjunto independente
     * @param universo Conjunto universo
     */
    private static void getIndependenteMaximo(Grafo independente, Grafo universo) {
	
	aumentarConjuntoIndependente(independente, universo);
	
	
	for (int r = 1; r < 81; r++) {
	    
	    /* Percorre vertices deste grafo */
	    for (java.util.Iterator i = universo.getVertices().iterator(); i.hasNext(); ) {
		Vertice v = (Vertice)i.next();
		
		if (independente.getTamanho() == 81)
		    return;
		
		if (!independente.possui(v)) {
		    Vertice conexao = independente.getUnicaConexao(v);
		    
		    if (conexao != null && conexao.getId() != -1) {
			
			independente.remover(conexao);
			independente.adicionar(v);
			
			aumentarConjuntoIndependente(independente, universo);
		    }
		}
	    }
	    
	}	
    }
}
